package cn.structure.linkedlist;

/**
 * 单向链表数据结构
 *
 * @author dunlingzi
 */
public class SinglyLinkedList {

    /**
     * 头节点
     */
    transient Node head;

    /**
     * 尾结点
     */
    transient Node last;

    /**
     * 链表实际长度
     */
    transient int size = 0;

    public SinglyLinkedList() {
    }

    /**
     * 链表节点
     */
    private static class Node {
        int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 链表增加操作
     *
     * @param data  插入链表数据
     * @param index 插入位置
     */
    public void add(int index, int data) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }

        Node addNode = new Node(data);
        //空链表
        if (size == 0) {
            head = addNode;
            last = addNode;
        } else if (index == 0) {
            //插入头节点
            addNode.next = head;
            head = addNode;
        } else if (size == index) {
            //插入尾结点
            last.next = addNode;
            last = addNode;
        } else {
            //中间插入
            Node preNode = get(index - 1);
            addNode.next = preNode.next;
            preNode.next = addNode;
        }
        size++;
    }

    /**
     * 链表更新操作
     *
     * @param data  插入链表数据
     * @param index 插入位置
     */
    public void edit(int index, int data) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        // 查找链表
        Node node = get(index);
        //更新数据
        node.data = data;
    }

    /**
     * 删除链表节点
     *
     * @param index 删除的位置
     * @return 删除的节点
     */
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node removeNode;
        //头部删除
        if (index == 0) {
            removeNode = head;
            head = head.next;
        } else if (index == size - 1) {
            // 尾部删除
            Node preNode = get(index - 1);
            removeNode = preNode.next;
            preNode.next = null;
            last = preNode;
        } else {
            //中间删除
            Node preNode = get(index - 1);
            Node nextNode = preNode.next.next;
            removeNode = preNode.next;
            preNode.next = nextNode;
        }
        // 将链表的大小自减
        size--;
        // 将头节点的指向指针指向null
        removeNode.next = null;
        return removeNode.data;
    }

    /**
     * 链表查找元素
     *
     * @param index 查找的位置
     * @return 节点
     */
    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 输出值
     */
    public void println() {
        StringBuilder sb = new StringBuilder();
        Node node = head;
        while (node != null) {
            sb.append(node.data).append(",");
            node = node.next;
        }
        System.out.println(sb);
    }
}
